package com.fallsvc.re.javasesets.carraylistlinkedlist;

import java.util.HashSet;

public class ListNode {
     int val;
     ListNode next;

     ListNode() {
     }

     ListNode(int val) {
         this.val = val;
     }

     ListNode(int val, ListNode next) {
         this.val = val;
         this.next = next;
     }
 }
class Solution1 {
//     递归合并两个链表
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        else if (l2 == null) {
            return l1;
        }
        else if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        }
        else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }

    }
// 找出交叉节点
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        HashSet<ListNode> set = new HashSet<>();
        ListNode tmp = headA;
        while(tmp != null) {
            set.add(tmp);
            tmp = tmp.next;
        }
        tmp = headB;
        while(tmp != null) {
            if(set.contains(tmp)) {
                return tmp;
            }
            tmp = tmp.next;
        }

        return null;
    }
}

